/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool travel(TreeNode *cur, int targetSum, int &path){
        //把当前结点的值放入path中
        path += cur -> val;
        // 遇到叶子结点，则判断是否满足返回条件
        if(cur -> left == NULL && cur -> right == NULL){
            if(path == targetSum) return true;            
        }
        if(cur -> left){
            bool LeftSum = travel(cur -> left, targetSum, path);
            // 需要判断函数的返回状态，不然程序会一直执行下去，最后返回false
            if(LeftSum == true){
                return true;
            }
            // 回溯，使用了引用传递，所以可以直接减去叶子结点值
            path -= cur -> left -> val;
        }
        if(cur -> right){
            bool RightSum = travel(cur -> right, targetSum, path);
            // 需要判断函数的返回状态，不然程序会一直执行下去，最后返回false
            if(RightSum == true){
                return true;
            }
            // 回溯，使用了引用传递，所以可以直接减去叶子结点值
            path -= cur -> right -> val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return false;
        // 存储路径上所有结点的值，以引用方式传递
        int path = 0;
        return travel(root, targetSum, path);
    }
};